#include <iostream>
#include <vector>

using namespace std;

// 23. 合并 K 个升序链表
// https://leetcode.cn/problems/merge-k-sorted-lists/description/

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *merge(ListNode *left, ListNode *right)
    {
        ListNode head(0);
        ListNode *curNode = &head;
        while (left != nullptr && right != nullptr)
        {
            if (left->val < right->val)
            {
                curNode->next = left;
                left = left->next;
            }
            else
            {
                curNode->next = right;
                right = right->next;
            }
            curNode = curNode->next;
        }

        if (left == nullptr)
        {
            curNode->next = right;
        }
        else
        {
            curNode->next = left;
        }
        return head.next;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        int n = lists.size();
        if (n == 0)
        {
            return nullptr;
        }
        ListNode *ans = nullptr;
        for (int i = 0; i < lists.size(); i++)
        {
            ans = merge(ans, lists[i]);
        }
        return ans;
    }
};

int main()
{
    return 0;
}
